ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpd/ballroom/ballroom.cpp

   1 #include <iostream>
   2 #include <cmath>
   3 #include <cstdio>
   4 #include <list>
   5 #include <utility>
   6 #include <cstdlib>
   7 #include <cassert>
   8 #include <complex>
   9
  10 #define forn(i, n) for (int i = 0; i < (n); i++)
  11 #define TOLERANCIA 1e-8
  12
  13 using namespace std;
  14
  15 struct MaybeDouble {
  16     long double valor;
  17     bool valido;
  18
  19     MaybeDouble(long double v, bool b): valor(v), valido(b) {};
  20 };
  21
  22 struct Vector {
  23     long double x;
  24     long double y;
  25
  26     Vector(long double xi, long double yi): x(xi), y(yi) {};
  27
  28     long double norma()  {
  29         return hypot(x, y);
  30     }
  31
  32     long double angulo() {
  33         return atan2(y, x);
  34     }
  35
  36 };
  37
  38 struct Columna {
  39     Vector posicion;
  40     long double radio;
  41
  42     Columna(long double x, long double y, long double r) : posicion(x,y), radio(r) {};
  43 };
  44
  45 typedef Vector Lampara;
  46 typedef pair<long double, long double> Intervalo;
  47 typedef pair<Vector, Vector> Segmento;
  48
  49
  50 inline long double largo(const Segmento& s) {
  51     return Vector(s.second.x - s.first.x, s.second.y - s.first.y).norma();
  52 }
  53
  54 inline long double largo(const Intervalo& i) {
  55     assert(i.first <= i.second);
  56     return i.second - i.first;
  57 }
  58
  59
  60 MaybeDouble intersect_segments(const Segmento& s1, const Segmento& s2) {
  61     Vector p1 = s1.first;
  62     Vector p2 = s1.second;
  63     Vector p3 = s2.first;
  64     Vector p4 = s2.second;
  65
  66     long double den = (p4.y-p3.y)*(p2.x-p1.x) - (p4.x-p3.x)*(p2.y-p1.y);
  67
  68     long double ua_num = (p4.x-p3.x)*(p1.y-p3.y) - (p4.y-p3.y)*(p1.x-p3.x);
  69     long double ub_num = (p2.x-p1.x)*(p1.y-p3.y) - (p2.y-p1.y)*(p1.x-p3.x);
  70
  71     if (fabs(den) < TOLERANCIA) {
  72         // Caso en que los segmentos son paralelos
  73         if (fabs(ua_num - ub_num) < TOLERANCIA && fabs(ub_num) < TOLERANCIA) {
  74             // Las rectas son coincidentes, esto no deberia ocurrir
  75             assert(false);
  76             return MaybeDouble((p1.norma() > p2.norma()? 0 : 1), true);
  77         }
  78         return MaybeDouble(0, false);
  79     }
  80
  81     if (ub_num/den >= 0) {
  82         return MaybeDouble(ua_num/den, true);
  83     }
  84     return MaybeDouble(0, false);
  85 }
  86
  87
  88 Intervalo interseccion_intervalos(const Intervalo& i1, const Intervalo& i2) {
  89
  90     long double d0 = max(i1.first, i2.first);
  91     long double d1 = min(i1.second, i2.second);
  92
  93     if (d1 < d0) {
  94         return Intervalo(0, 0);
  95     } else {
  96         return Intervalo(d0, d1);
  97     }
  98 }
  99
 100
 101 Intervalo rango_oscurecido(const Segmento& pared, const Lampara& lampara, const Columna& columna) {
 102     Vector bisectriz(columna.posicion.x - lampara.x, columna.posicion.y - lampara.y);
 103     long double p = asin(columna.radio/bisectriz.norma());
 104     long double alpha = bisectriz.angulo();
 105
 106     Vector d1(cos(alpha + p), sin(alpha + p));
 107     Vector d2(cos(alpha - p), sin(alpha - p));
 108
 109     MaybeDouble p1 = intersect_segments(pared, Segmento(lampara, Vector(lampara.x + d1.x, lampara.y + d1.y)));
 110     MaybeDouble p2 = intersect_segments(pared, Segmento(lampara, Vector(lampara.x + d2.x, lampara.y + d2.y)));
 111
 112     long double unidad = largo(pared);
 113
 114     // Se sabe que los puntos de interseccion estan ordenados correctamente
 115     // porque el angulo de diferencia entre las semirectas es menor a 180,
 116     // entonces no es necesario chequearlo.
 117     Intervalo res;
 118
 119     if (!p1.valido) {
 120         if (!p2.valido) {
 121             return Intervalo(0, 0);
 122         } else {
 123             res = Intervalo(0, p2.valor);
 124         }
 125     } else {
 126         if (!p2.valido) {
 127             res = Intervalo(p1.valor, 1);
 128         } else {
 129             res = Intervalo(p1.valor, p2.valor);
 130         }
 131     }
 132
 133     res = interseccion_intervalos(res, Intervalo(0,1));
 134     return Intervalo(res.first * unidad, res.second * unidad);
 135 }
 136
 137 void invertir_rango(const list<Intervalo>& ints, long double fin, list<Intervalo>& out) {
 138
 139     if (!ints.size()) {
 140         out.push_back(Intervalo(0,fin));
 141         return;
 142     }
 143
 144
 145     list<Intervalo>::const_iterator it = ints.begin();
 146     if (it->first > 0) {
 147         out.push_back(Intervalo(0, it->first));
 148     }
 149
 150     it++;
 151
 152     list<Intervalo>::const_iterator itprev = ints.begin();
 153     while (it != ints.end()) {
 154         out.push_back(Intervalo(itprev->second, it->first));
 155         it++;
 156         itprev++;
 157     }
 158
 159     if (itprev->second < fin) {
 160         out.push_back(Intervalo(itprev->second, fin));
 161     }
 162 }
 163
 164
 165 void reduce_union(list<Intervalo>& l_o, list<Intervalo>& out) {
 166     // elimino repetidos para acelerar el sort
 167     list<Intervalo> l;
 168
 169     for (list<Intervalo>::const_iterator itcito = l_o.begin(); itcito != l_o.end(); itcito++) {
 170         if (itcito->first < itcito->second) {
 171             l.push_back(Intervalo(itcito->first, itcito->second));
 172         } else if (itcito->first > itcito->second) {
 173             assert(false);
 174         }
 175     }
 176
 177
 178     if (!l.size()) return;
 179
 180     l.sort();
 181
 182     list<Intervalo>::const_iterator it = l.begin();
 183     Intervalo cand = *it;
 184     Intervalo otro;
 185
 186     it++;
 187     while (it != l.end()) {
 188         otro = *it;
 189         if (otro.first < otro.second) {
 190             if (otro.first > cand.second) {
 191                 out.push_back(cand);
 192                 cand = otro;
 193             } else {
 194                 if (otro.second > cand.second) {
 195                     cand = Intervalo(cand.first, otro.second);
 196                 }
 197             }
 198         }
 199         it++;
 200     }
 201
 202     out.push_back(cand);
 203 }
 204
 205
 206 long double resolver(const list<Lampara>& lamparas, const list<Columna>& columnas, int max_x, int max_y) {
 207     list<Segmento> paredes;
 208     paredes.push_back(Segmento(Vector(0,0), Vector(0, max_y)));
 209     paredes.push_back(Segmento(Vector(0,max_y), Vector(max_x, max_y)));
 210     paredes.push_back(Segmento(Vector(max_x,max_y), Vector(max_x, 0)));
 211     paredes.push_back(Segmento(Vector(max_x,0), Vector(0, 0)));
 212
 213     long double total = 0;
 214
 215     for (list<Segmento>::iterator p = paredes.begin(); p != paredes.end(); p++) {
 216         list<Intervalo> luces_pared;
 217         for (list<Lampara>::const_iterator l = lamparas.begin(); l != lamparas.end(); l++) {
 218             list<Intervalo> zonas_tapadas;
 219             for (list<Columna>::const_iterator c = columnas.begin(); c != columnas.end(); c++) {
 220                 zonas_tapadas.push_back(rango_oscurecido(*p, *l, *c));
 221             }
 222
 223             list<Intervalo> tapadas_unidas;
 224             list<Intervalo> zona_iluminada;
 225
 226             reduce_union(zonas_tapadas, tapadas_unidas);
 227             invertir_rango(tapadas_unidas, largo(*p), zona_iluminada);
 228
 229             luces_pared.splice(luces_pared.end(), zona_iluminada);
 230         }
 231
 232         list<Intervalo> luces_pared_unidas;
 233         reduce_union(luces_pared, luces_pared_unidas);
 234
 235         for (list<Intervalo>::iterator it = luces_pared_unidas.begin(); it != luces_pared_unidas.end(); it++) {
 236             total += largo(*it);
 237         }
 238     }
 239
 240     return total;
 241 }
 242
 243
 244 int main() {
 245
 246     int nl, nc, max_x, max_y;
 247
 248     for (;;) {
 249         scanf("%d %d %d %d", &nl, &nc, &max_x, &max_y);
 250
 251         if (!(nl || nc || max_x || max_y)) {
 252             break;
 253         }
 254
 255         list<Vector> lamparas;
 256         list<Columna> columnas;
 257
 258         int x, y, r;
 259
 260         forn(i, nl) {
 261             scanf("%d %d", &x, &y);
 262             lamparas.push_back(Lampara(x,y));
 263         }
 264
 265         forn(i, nc) {
 266             scanf("%d %d %d", &x, &y, &r);
 267             columnas.push_back(Columna(x, y, r));
 268         }
 269
 270         printf("%.4Lf\n", resolver(lamparas, columnas, max_x, max_y));
 271     }
 272 }